package org.xingole.leetcode.dp.knapsack;

/*
 * Problem:
 * 
 * There is a group of n members, and a list of various crimes they could commit. The 
 * i-th crime generates a 'profit[i]' and requires 'group[i]' members to participate
 * in it. If a member participates in one crime, that member can't participate in 
 * another crime.
 * 
 * Let's call a profitable scheme any subset of these crimes that generates at lest
 * 'minProfit' profit, and the total number of members participating in that subset 
 * of crimes is at most 'n'.
 * 
 * Return the number of schemes that can be chosen. Since the answer may be very 
 * large, return it modul '10^9 + 7'.
 * 
 * 
 */

public class ProfitableSchemes {

     /*
      *  
      * Approach: Dynamic Programming
      *
      * We have two list, each of size m: 
      *   1. 'group': represents the number of members that each of the m crimes needs;
      *   2. 'profits': represesnts the profit that each crime generates. 
      * We need to find the number of subsets of these crimes such that a subset has 
      * no more than n criminals in it, and the total profit has to be at least 'minProfit'.
      *
      * 1. Determine the problem substructure. 
      * 
      * Each of the m crimes in the list has two options:
      *   1. either we consider it in the current subset, 
      *   2. or we don't.
      * 
      * If we add this crime to the subset, we need to ensure:
      *   1. first that the number of members doesn't exceed n;
      *   2. also, the total profit will be increased by the profit of this crime.
      * If we don't consider this crime, there would be no change in the number of 
      * members or the total profit. 
      * 
      * The total number of such subsets would be the sum of the count of these two 
      * choices for each crime.
      *
      * Let dp[i][j][k] represents the number of ways to get profitable 
      * scheme by selecting subset from first i crimes including j members
      * while the total profit is at least k.
      *
      * Therefore, the ultimate answer is 
      *      ans = sum(dp[m][j][minProfit]) for j = 0 ... n
      *
      * 2. Recusively solve the problem
      * 
      * Base case:
      *      dp[0][0][0] = 1, trival situation.
      * Inductive case:
      *    if we doesn't or cann't include the ith crime, 
      *       dp[i][j][k] = dp[i-1][j][k]
      *    if we can include the ith crime (conditionally)
      *       dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i]][max(0, k-profit[i])]
      *
      */
     private static final int MOD = (int) (1e9 + 7);
     public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
          int m = group.length;
          
          int[][][]  dp = new int[m + 1][n + 1][minProfit + 1];

          // Base case:
          dp[0][0][0] = 1;

          // Bottom-to-Up style
          for ( int i = 1; i <= m; i++ ) {
               int members = group[i - 1];
               int profits = profit[i - 1];

               for ( int j = 0; j <= n; j++ ) {
                    for ( int k = 0; k <= minProfit; k++ ) {
                         dp[i][j][k] = dp[i-1][j][k];
                         // condition that enable including the ith crime.
                         if ( j >= members ) {
                              dp[i][j][k] += dp[i - 1][j - members][Math.max(0, k - profits)];
                         }

                         dp[i][j][k] %= MOD;
                    }
               }
          }

          int ans = 0;
          for (int j = 0; j <= n; j++) {
               ans  += dp[m][j][minProfit];
               ans %= MOD;
          }
          return ans;
     }

     public static void main(String[] args) {
          ProfitableSchemes ps = new ProfitableSchemes();

          int n, minProfit;
          int[] group, profit;

          // Example 1:
          // Input: n = 5, minProfit = 3, group = [2, 2], profit = [2, 3]
          n = 5; minProfit = 3; group = new int[]{2, 2}; profit = new int[]{2, 3};

          System.out.println(
               "Example 1 Output: " + 
               ps.profitableSchemes(n, minProfit, group, profit) 
          );

          // Example 2: 
          // Input: n = 10, minProfit = 5, group = [2, 3, 5], profit = [6, 7, 8]
          n = 10; minProfit = 5; group = new int[]{2, 3, 5}; profit = new int[]{6, 7, 8};

          System.out.println(
               "Example 2 Output: " + 
               ps.profitableSchemes(n, minProfit, group, profit)
          );

     }

}
